home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_12_10 / allison / xref.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-06  |  3.3 KB  |  148 lines
  1. LISTING 7
  2. /* xref.c:  Prints line numbers where each word occurs */
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include <assert.h>
  7.  
  8. #define WORD_WIDTH 15
  9.  
  10. /* Node structure for each list of line numbers */
  11. struct List
  12. {
  13.     int lnum;
  14.     struct List *next;
  15. };
  16. typedef struct List List;
  17.  
  18. /* Node structure for tree of distinct words */
  19. struct Tree
  20. {
  21.     char word[WORD_WIDTH];
  22.     List *lstptr;
  23.     struct Tree *left,*right;
  24. };
  25. typedef struct Tree Tree;
  26.  
  27. /* Tree and list functions */
  28. Tree *addword(Tree *, char *);
  29. List *addline(List *, int);
  30. Tree *find_node(Tree *, char *);
  31. void print_tree(Tree *t);
  32. void print_list(List *);
  33.  
  34. int  ndistinct = 0;
  35.  
  36. main(int argc, char *argv[])
  37. {
  38.     char linebuf[BUFSIZ];
  39.     Tree *words = NULL;
  40.     int lineno = 0;
  41.  
  42.     /* Do optional input redirection */
  43.     if (argc > 1)
  44.         assert(freopen(argv[1],"r",stdin));
  45.  
  46.     /* Process each line of text file */
  47.     while (fgets(linebuf,BUFSIZ,stdin) != NULL)
  48.     {
  49.         char *wordptr, *lineptr = linebuf;
  50.         char *bad_chars = " \t\n\f\v\\\"~!@#$%^&*()+'"
  51.                           "|`1234567890-=\{}[]:;<>?,./";
  52.  
  53.         ++lineno;
  54.  
  55.         /* Process each word in line */
  56.         while ((wordptr = strtok(lineptr,bad_chars)) != NULL)
  57.         {
  58.             Tree *node;
  59.  
  60.             words = addword(words,wordptr);
  61.             node = find_node(words,wordptr);
  62.             node->lstptr = addline(node->lstptr,lineno);
  63.             lineptr = NULL;
  64.         }
  65.     }
  66.  
  67.     /* Print results */
  68.     printf("No. of distinct words: %d\n\n",ndistinct);
  69.     print_tree(words);
  70.     return 0;
  71. }
  72.  
  73. Tree *addword(Tree *tp, char *word)
  74. {
  75.     if (tp == NULL)
  76.     {
  77.         /* Add new entry */
  78.         ++ndistinct;
  79.         tp = malloc(sizeof(Tree));
  80.         strncpy(tp->word,word,WORD_WIDTH)[WORD_WIDTH] = '\0';
  81.         tp->left = tp->right = NULL;
  82.         tp->lstptr = NULL;
  83.     }
  84.     else if (strcmp(tp->word,word) < 0)
  85.         tp->right = addword(tp->right,word);
  86.     else if (strcmp(tp->word,word) > 0)
  87.         tp->left = addword(tp->left,word);
  88.  
  89.     return tp;
  90. }
  91.  
  92. List *addline(List *lp, int n)
  93. {
  94.     if (lp == NULL)
  95.     {
  96.         /* Append new line number to list */
  97.         List *newp = malloc(sizeof(List));
  98.         assert(newp);
  99.         newp->lnum = n;
  100.         newp->next = NULL;
  101.         return newp;
  102.     }
  103.     else if (lp->lnum != n)
  104.         lp->next = addline(lp->next,n);
  105.  
  106.     return lp;
  107. }
  108.  
  109. void print_tree(Tree *tp)
  110. {
  111.     if (tp != NULL)
  112.     {
  113.         /* Inorder traversal */
  114.         print_tree(tp->left);
  115.         printf("%-*.*s: ",WORD_WIDTH,WORD_WIDTH,tp->word);
  116.         print_list(tp->lstptr); putchar('\n');
  117.         print_tree(tp->right);
  118.     }
  119. }
  120.  
  121. void print_list(List *lp)
  122. {
  123.     const int NUM_WIDTH = 5;
  124.     const int INDENT = WORD_WIDTH + 2;
  125.     const int NUMS_PER_LINE = 8;
  126.     int count;
  127.  
  128.     for (count = 0; lp != NULL; lp = lp->next, ++count)
  129.     {
  130.         printf("%*d",NUM_WIDTH,lp->lnum);
  131.         if ((count+1) % NUMS_PER_LINE == 0
  132.              && lp->next != NULL)
  133.             printf("\n%*c",INDENT,' ');
  134.     }
  135. }
  136.  
  137. Tree *find_node(Tree *tp, char *s)
  138. {
  139.     /* Binary search for word */
  140.     if (strcmp(tp->word,s) > 0)
  141.         return find_node(tp->left,s);
  142.     else if (strcmp(tp->word,s) < 0)
  143.         return find_node(tp->right,s);
  144.     else
  145.         return tp;
  146. }
  147.  
  148.